package DoExercise.HSP_ZCY.A008_树.A001_普通二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: Du
 * @Date: 2021/7/13 12:20
 */
public class C08_序列化和反序列化二叉树
{
    
    public static void main(String[] args)
    {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++)
        {
            Node head = generateRandomBST(maxLevel, maxValue);
            Queue<String> pre = preSerial(head);
            Queue<String> level = levelSerial(head);
            Node preBuild = buildByPreQueue(pre);
            Node levelBuild = buildByLevelQueue(level);
            if (!isSameValueStructure(preBuild, levelBuild))
            {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
    
    
    public static class Node
    {
        public int value;
        public Node left;
        public Node right;
        
        public Node(int data)
        {
            this.value = data;
        }
    }
    
    /**
     * 先序方式序列化
     *
     * @param head
     * @return
     */
    public static Queue<String> preSerial(Node head)
    {
        Queue<String> ans = new LinkedList<>();
        pres(head, ans);
        return ans;
    }
    
    public static void pres(Node head, Queue<String> ans)
    {
        if (head == null)
        {
            ans.add(null);
        } else
        {
            ans.add(String.valueOf(head.value));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }
    
    
    /**
     * 先序方式反序列化
     *
     * @param prelist
     * @return
     */
    public static Node buildByPreQueue(Queue<String> prelist)
    {
        if (prelist == null || prelist.size() == 0) return null;
        return preb(prelist);
    }
    
    public static Node preb(Queue<String> prelist)
    {
        String value = prelist.poll();
        if (value == null) return null;
        Node head = new Node(Integer.valueOf(value));
        head.left = preb(prelist);
        head.right = preb(prelist);
        return head;
    }
    
    
    /**
     * 按层序列化
     *
     * @param head
     * @return
     */
    public static Queue<String> levelSerial(Node head)
    {
        Queue<String> ans = new LinkedList<>();
        if (head == null)
        {
            ans.add(null);
        } else
        {
            ans.add(String.valueOf(head.value));
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty())
            {
                head = queue.poll();
                //序列化左树
                if (head.left != null)
                {
                    ans.add(String.valueOf(head.left.value));
                    queue.add(head.left);
                } else
                {
                    ans.add(null);
                }
                //序列化右树
                if (head.right != null)
                {
                    ans.add(String.valueOf(head.right.value));
                    queue.add(head.right);
                } else
                {
                    ans.add(null);
                }
            }
        }
        return ans;
    }
    
    /**
     * 反序列化，层序方式
     *
     * @param levelList
     * @return
     */
    public static Node buildByLevelQueue(Queue<String> levelList)
    {
        if (levelList == null || levelList.size() == 0) return null;
        Node head = generateNode(levelList.poll());
        Queue<Node> queue = new LinkedList<>();
        if (head != null)
        {
            queue.add(head);
        }
        Node node = null;
        while (!queue.isEmpty())
        {
            node = queue.poll();
            //无论是否为null，节点都需要创建，如果是null，就创建一个null节点，不是null，就创建对应的节点，并将其作为子节点加入到队列中
            node.left = generateNode(levelList.poll());
            node.right = generateNode(levelList.poll());
            if (node.left != null)
            {
                queue.add(node.left);
            }
            if (node.right != null)
            {
                queue.add(node.right);
            }
        }
        return head;
    }
    
    public static Node generateNode(String val)
    {
        if (val == null) return null;
        return new Node(Integer.valueOf(val));
    }
    
    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue)
    {
        return generate(1, maxLevel, maxValue);
    }
    
    // for test
    public static Node generate(int level, int maxLevel, int maxValue)
    {
        if (level > maxLevel || Math.random() < 0.5)
        {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }
    
    // for test
    public static boolean isSameValueStructure(Node head1, Node head2)
    {
        if (head1 == null && head2 != null)
        {
            return false;
        }
        if (head1 != null && head2 == null)
        {
            return false;
        }
        if (head1 == null && head2 == null)
        {
            return true;
        }
        if (head1.value != head2.value)
        {
            return false;
        }
        return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
    }
    
    
    /**
     * 生成一个二叉树，从上向下顺序
     * 0
     * 1   2
     * 3  4  5  6
     *
     * @return
     */
    public Node[] CreateBinaryTree(int size)
    {
        Node[] root = new Node[size];
        for (int i = 0; i < size; i++)
        {
            root[i] = new Node(i);
        }
        
        for (int i = 0; i < size; i++)
        {
            if (i * 2 + 1 < size)
            {
                root[i].left = root[i * 2 + 1];
            }
            
            if (i * 2 + 2 < size)
            {
                root[i].right = root[i * 2 + 2];
            }
        }
        return root;
    }
}
